
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1657. -- [Usaco2006 Mar]Mooo -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1657: [Usaco2006 Mar]Mooo</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>239&nbsp;&nbsp;<span class=green>Solved: </span>162<br>[<a href='submitpage.php?id=1657'>Submit</a>][<a href='problemstatus.php?id=1657'>Status</a>][<a href='bbs.php?id=1657'>Discuss</a>]</center><h2>Description</h2><div class=content>Farmer John's N (1 <= N <= 50,000) cows are standing in a very
straight row and mooing. Each cow has a unique height h in the range
1..2,000,000,000 nanometers (FJ really is a stickler for precision).
Each cow moos at some volume v in the range 1..10,000. This "moo"
travels across the row of cows in both directions (except for the
end cows, obviously). Curiously, it is heard only by the closest
cow in each direction whose height is strictly larger than that of
the mooing cow (so each moo will be heard by 0, 1 or 2 other cows,
depending on not whether or taller cows exist to the mooing cow's
right or left).

The total moo volume heard by given cow is the sum of all the moo
volumes v for all cows whose mooing reaches the cow. Since some
(presumably taller) cows might be subjected to a very large moo
volume, FJ wants to buy earmuffs for the cow whose hearing is most
threatened. Please compute the loudest moo volume heard by any cow.


Farmer John的N(1<=N<=50,000)头奶牛整齐地站成一列“嚎叫”。每头奶牛有一个确定的高度h(1<=h<=2000000000)，叫的音量为v (1<=v<=10000)。每头奶牛的叫声向两端传播，但在每个方向都只会被身高严格大于它的最近的一头奶牛听到，所以每个叫声都只会 被0，1，2头奶牛听到（这取决于它的两边有没有比它高的奶牛）。

一头奶牛听到的总音量为它听到的所有音量之和。自从一些奶牛遭受巨大的音量之后，Farmer John打算买一个耳罩给被残害得最厉 害的奶牛，请你帮他计算最大的总音量。
</div><h2>Input</h2><div class=content>* Line 1: A single integer, N.

* Lines 2..N+1: Line i+1 contains two space-separated integers, h and
        v, for the cow standing at location i.

</div><h2>Output</h2><div class=content>* Line 1: The loudest moo volume heard by any single cow.
</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>3<br />
4 2<br />
3 5<br />
6 10<br />
<br />
INPUT DETAILS:<br />
<br />
Three cows: the first one has height 4 and moos with volume 2, etc.<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>7<br />
<br />
OUTPUT DETAILS:<br />
<br />
The third cow hears both the first and second cows moo 2+5=7.  Though the<br />
third cow moos with volume 10, no one hears her.<br />
</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Silver'>Silver</a></p></div><center>[<a href='submitpage.php?id=1657'>Submit</a>][<a href='problemstatus.php?id=1657'>Status</a>][<a href='bbs.php?id=1657'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
